/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-05
 * Time:21:24
 */

/**
 * 力扣剑指offer10-2:青蛙跳台问题
 */

public class numWays {
    /**
     * 动态规划
     * 类似于斐波那契问题
     * @param n
     * @return
     */
    public int numWays(int n) {
        int p = 1;
        int q = 1;
        int sum = 0;
        for(int i = 0;i < n;i++){
            //1000000007是题目要求
            sum = (p + q) % 1000000007;
            p = q;
            q = sum;
        }
        return p;
    }
}
